|
Queueing theory is the mathematical study of waiting lines, or queues. In queueing theory a model is constructed so that queue lengths and waiting time can be predicted.〔 Queueing theory is generally considered a branch of operations research because the results are often used when making business decisions about the resources needed to provide a service. Queueing theory has its origins in research by Agner Krarup Erlang when he created models to describe the Copenhagen telephone exchange.〔 The ideas have since seen applications including telecommunication, traffic engineering, computing〔(【引用サイトリンク】 first = Daniel A. Menasce )〕 and the design of factories, shops, offices and hospitals. ==Single queueing nodes== Single queueing nodes are usually described using Kendall's notation in the form ''A''/''S''/''C'' where ''A'' describes the time between arrivals to the queue, ''S'' the size of jobs and ''C'' the number of servers at the node.〔Tijms, H.C, ''Algorithmic Analysis of Queues", Chapter 9 in A First Course in Stochastic Models, Wiley, Chichester, 2003〕 Many theorems in queueing theory can be proved by reducing queues to mathematical systems known as Markov chains, first described by Andrey Markov in his 1906 paper.〔A.A. Markov, Extension of the law of large numbers to dependent quantities, Izvestiia Fiz.-Matem. Obsch. Kazan Univ., (2nd Ser.), 15(1906), pp. 135–156 .〕 Agner Krarup Erlang, a Danish engineer who worked for the Copenhagen Telephone Exchange, published the first paper on what would now be called queueing theory in 1909.〔(【引用サイトリンク】title=Agner Krarup Erlang (1878 - 1929) | plus.maths.org )〕 He modeled the number of telephone calls arriving at an exchange by a Poisson process and solved the M/D/1 queue in 1917 and M/D/k queueing model in 1920. In Kendall's notation: * M stands for Markov or memoryless and means arrivals occur according to a Poisson process * D stands for deterministic and means jobs arriving at the queue require a fixed amount of service * ''k'' describes the number of servers at the queueing node (''k'' = 1, 2,...). If there are more jobs at the node than there are servers then jobs will queue and wait for service The M/M/1 queue is a simple model where a single server serves jobs that arrive according to a Poisson process and have exponentially distributed service requirements. In an M/G/1 queue the G stands for general and indicates an arbitrary probability distribution. The M/G/1 model was solved by Felix Pollaczek in 1930,〔Pollaczek, F., Ueber eine Aufgabe der Wahrscheinlichkeitstheorie, Math. Z. 1930〕 a solution later recast in probabilistic terms by Aleksandr Khinchin and now known as the Pollaczek–Khinchine formula.〔〔 After World War II queueing theory became an area of research interest to mathematicians. In 1953 David Kendall solved the GI/M/k queue〔Kendall, D.G.:Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain, Ann. Math. Stat. 1953〕 and introduced the modern notation for queues, now known as Kendall's notation. In 1957 Pollaczek studied the GI/G/1 using an integral equation.〔Pollaczek, F., Problèmes Stochastiques posés par le phénomène de formation d'une queue〕 John Kingman gave a formula for the mean waiting time in a G/G/1 queue: Kingman's formula. The matrix geometric method and matrix analytic methods have allowed queues with phase-type distributed inter-arrival and service time distributions to be considered. Problems such as performance metrics for the M/G/k queue remain an open problem.〔〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Queueing theory」の詳細全文を読む スポンサード リンク
|